/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.dp;

/**
 * <p>二维数组的最小路径和</p>
 * @author towan
 * @email tongwenzide@163.com
 * @time 2015年5月30日
 */
public class MinPathSum {

    public int minPathSum(int[][] grid) {
        if(grid==null || grid.length==0 || grid[0].length==0){
           return 0;
       }
       int m = grid.length;
       int n = grid[0].length;
       int path[][] = new int[m][n];
       path[0][0] = grid[0][0];
       //左边界
       for(int i=1;i<m;i++){
           path[i][0] = path[i-1][0]+grid[i][0];
       }
       //顶部边界
       for(int j=1;j<n;j++){
           path[0][j] = path[0][j-1]+grid[0][j];
       }
       for(int i=1;i<m;i++){
           for(int j=1;j<n;j++){
               //计算从左过来的路径和从上面下来的路径和
               path [i][j] = Math.min(path[i][j-1]+grid[i][j], path[i-1][j]+grid[i][j]);
           }
       }
       
       return path[m-1][n-1];
   }
}
